/*
Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)
*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

bool checkInterleave(const string &a, const string &b, const string &c)
{
   if (a.size() + b.size() != c.size()) return false;

   int i = 0, j = 0, k = 0;
   while( i < a.size() || j < b.size()) {
    if (i < a.size() && a[i] == c[k]) i++;
    else if (j < b.size() && b[j] == c[k]) j++;
    else return false;
    k++;
  }
  return true;
}


int main(int argc, char **argv)
{
    cout << checkInterleave("abcd", "xyz", "axybczd") << endl;
    cout << checkInterleave("", "xyz", "axybczd") << endl;
    cout << checkInterleave("abud", "xyz", "axybczd") << endl;
    cout << checkInterleave("ab", "xyz", "axybczd") << endl;
}
